package com.hdu.other.unionSet;

import java.util.HashMap;
import java.util.Map;

public class lc974 {

    public static void main(String[] args) {

        int[][] stones = new int[][]{{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
        System.out.println(new lc974().new Solution().removeStones(stones));
    }

    class Solution {
        int n = 0;
        int m = 0;
        int[] father = null;
        public int removeStones(int[][] stones) {

            int n = stones.length;
            m = n;
            this.father = new int[n];
            build();
            Map<Integer, Integer> firstRowMeet = new HashMap<>();
            Map<Integer, Integer> firstColMeet = new HashMap<>();

            for (int i = 0; i < n; i++)
            {
                int row = stones[i][0];
                int col = stones[i][1];

                if (firstRowMeet.containsKey(row))
                {
                    union(i, firstRowMeet.get(row));
                }
                else
                {
                    firstRowMeet.put(row, i);
                }

                if (firstColMeet.containsKey(col))
                {
                    union(i, firstColMeet.get(col));
                }
                else
                {
                    firstColMeet.put(col, i);
                }
            }


            return n - m;
        }

        void build()
        {
            for (int i = 0; i < n; i++)
            {
                father[i] = i;
            }
        }

        void union(int x, int y)
        {
            if (find(x) != find(y))
            {
                father[find(x)] = find(y);
                m--;
            }
        }

        int find(int x)
        {
            if (father[x] != x)
            {
                father[x] = find(father[x]);
            }
            return father[x];

        }
    }
}
